#define _CRT_SECURE_NO_WARNINGS 1


#include "BinaryTree.h"

//BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
//{
//
//}

//void BinaryTreeDestory(BTNode** root);

//BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}


int BinaryTreeLevelSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLevelSize(root->left) + BinaryTreeLevelSize(root->right);
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1)+
			 BinaryTreeLevelKSize(root->right, k - 1);
}
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftHeight = BinaryTreeHeight(root->left);
	int rightRight = BinaryTreeHeight(root->right);

	return leftHeight > rightRight ? leftHeight + 1 : rightRight + 1;

}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);

}
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePrevOrder(root->left);
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->right);
}
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%d ", root->data);
}
int BinaryTreeComplete(BTNode* root);

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}


